package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-21 22:10
 */

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * 迷宫问题bfs
 * <p>
 * 广度优先遍历矩阵。代价相同的图中，广度优先遍历可以保证遍历到的目标点就是经过最短路径到达的点。
 * 为此，我们可以创建一个Point类，属性为横纵坐标和父节点。
 * 从（0，0）出发，将经过的坐标点都设为1，避免重复经过而进入死循环。
 * 把当前点的上下左右值为0的点都加入队列中，直到遇见出口为止。
 * 遇到出口时，pos的father路径就是最短路径的逆路径。此时只需要把逆路径反转一下即可。
 */
public class HJ43bfs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }

            // Queue要使用offer()来加入元素，使用poll()来获取并移出元素。
            //LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
            //element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
            //　　offer       添加一个元素并返回true       如果队列已满，则返回false
            //　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
            //　　peek       返回队列头部的元素             如果队列为空，则返回null
            //　　put         添加一个元素                      如果队列满，则阻塞
            //　　take        移除并返回队列头部的元素     如果队列为空，则阻塞
            Queue<Point> que = new LinkedList<>();
            que.offer(new Point(0, 0, null));
            //将初始位置标记为已走
            arr[0][0] = 1;
            Point pos = null;
            while (true) {
                pos = que.poll();// 移除并返问队列头部的元素
                int x = pos.x;
                int y = pos.y;

                if (x == n - 1 && y == m - 1) {
                    break;
                } else {
                    //向下
                    if (x + 1 < n && arr[x + 1][y] == 0) {
                        arr[x + 1][y] = 1;
                        que.offer(new Point(x + 1, y, pos));//添加一个元素，并返回true
                    }
                    //向右
                    if (y + 1 < m && arr[x][y + 1] == 0) {
                        arr[x][y + 1] = 1;
                        que.offer(new Point(x, y + 1, pos));
                    }
                    //向上
                    if (x - 1 > n && arr[x - 1][y] == 0) {
                        arr[x - 1][y] = 1;
                        que.offer(new Point(x - 1, y, pos));
                    }
                    //向左
                    if (y - 1 > m && arr[x][y - 1] == 0) {
                        arr[x][y - 1] = 1;
                        que.offer(new Point(x, y - 1, pos));
                    }
                }
            }

            //获取的链表是倒序的，将它放入栈中，先进的后出，变为正序；
            Stack<Point> stack = new Stack<Point>();
            while (pos != null) {
                stack.push(pos);
                pos = pos.father;
            }

            while (!stack.isEmpty()) {
                Point temp = stack.peek();//返回栈顶的元素但是不移除它
                stack.pop();
                System.out.println("(" + temp.x + "," + temp.y + ")");
            }

        }

    }

    //简单的位置类
    public static class Point {
        int x;
        int y;
        Point father;

        public Point(int x, int y, Point father) {
            this.x = x;
            this.y = y;
            this.father = father;
        }

    }
}

//********利用递归可以后序输出链表的特性，可以省去反转路径的操作：
//class Point{
//    int px;
//    int py;
//    Point father;
//    Point(int px,int py,Point father){
//        this.px=px;
//        this.py=py;
//        this.father = father;
//    }
//    Point(){}
//}
//public  class Main{

//    //利用递归可以后序输出链表的特性，可以省去反转路径的操作
//    public static void print(Point p){
//        if(p != null){
//            print(p.father);
//            System.out.println("("+p.px+","+p.py+")");
//        }
//    }

//    public  static void main(String args[]){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int row = sc.nextInt();
//            int col = sc.nextInt();
//            int [][] grid = new int[row][col];
//            for(int i=0;i<row;++i){
//                for(int j=0;j<col;++j){
//                    grid[i][j]=sc.nextInt();
//                }
//            }
//            Queue<Point> que = new LinkedList<Point>();
//            que.offer(new Point(0,0,null));
//            grid[0][0]=1;
//            Point pos = null;
//            while(true){
//                pos = que.poll();
//                int px = pos.px;
//                int py = pos.py;
//                if(px==row-1&&py==col-1)break;
//                else {
//                    if(px+1<row&&grid[px+1][py]==0){
//                        grid[px+1][py]=1;
//                        que.offer(new Point(px+1,py,pos));
//                    }
//                    if(py-1>=0&&grid[px][py-1]==0){
//                        grid[px][py-1]=1;
//                        que.offer(new Point(px,py-1,pos));
//                    }
//                    if(px-1>=0&&grid[px-1][py]==0){
//                        grid[px-1][py]=1;
//                        que.offer(new Point(px-1,py,pos));
//                    }
//                    if(py+1<col&&grid[px][py+1]==0){
//                        grid[px][py+1]=1;
//                        que.offer(new Point(px,py+1,pos));
//                    }
//                }
//            }
//            print(pos);
//        }
//    }
//}
